Jeg skriver for øyeblikket en grunnleggende parser for en XML-smak. Som en øvelse implementerer jeg en LL-borddrevet parser. Dette er mitt eksempel på BNF-grammatikk: % tokenavn datastreng %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: name attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | data elem_or_data | / * epsilon * / ; attr: name ":" string attr | / * epsilon * / ; Er denne grammatikken riktig? Hver terminal bokstavelig er mellom anførselstegn. De abstrakte terminalene er spesifisert av% token. Jeg koder en håndskrevet lexer for å konvertere innspillene mine til en tokenliste. Hvordan skulle jeg tokenisere de abstrakte terminalene?
2021-03-03 08:11:59
Den klassiske tilnærmingen ville være å skrive et vanlig uttrykk (eller annen gjenkjenning) for hver mulig terminal.
Det du kaller "abstrakte" terminaler, som er helt konkrete, er faktisk terminaler hvis tilknyttede mønstre gjenkjenner mer enn en mulig inngangsstreng. Strengen som faktisk er gjenkjent (eller en eller annen beregnet funksjon av den strengen) skal sendes til parseren som symbolets semantiske verdi.
Nominelt, på hvert punkt i inngangsstrengen, kjører tokeniser alle gjenkjennere og velger den som har lengst samsvar. (Dette er den såkalte "maksimale munch" -regelen.) Dette kan vanligvis optimaliseres, spesielt hvis alle mønstrene er vanlige uttrykk. (F) lex vil gjøre den optimaliseringen for deg, for eksempel.
En komplikasjon i ditt tilfelle er at tokeniseringen av språket ditt er kontekstavhengig. Spesielt når målet er elem_or_data, er de eneste mulige tokens <,